package com.leetcode.algorithm.y22.m08.w3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 187. 重复的DNA序列
 * 
 * https://leetcode.cn/problems/repeated-dna-sequences/
 * 
 * @author jie.deng
 *
 */
class Question0187Solution02 {

	public List<String> findRepeatedDnaSequences(String s) {
		int len = s.length();
		List<String> result = new ArrayList<>();
		if (len <= 10) {
			return result;
		}
		int[] arr = new int['T' - 'A' + 1];
		arr[0] = 0;
		arr['C' - 'A'] = 1;
		arr['G' - 'A'] = 2;
		arr['T' - 'A'] = 3;
		Map<Integer, Integer> numMap = new HashMap<>(len);
		int idx = 0;
		int num = 0;
		while (idx < 9) {
			num <<= 2;
			num |= arr[s.charAt(idx) - 'A'];
			idx++;
		}

		while (idx < len) {
			num <<= 2;
			num |= arr[s.charAt(idx) - 'A'];
			if (!numMap.containsKey(num)) {
				numMap.put(num, 1);
			} else {
				int cnt = numMap.get(num).intValue();
				if (cnt == 1) {
					result.add(s.substring(idx - 9, idx + 1));
				}
				numMap.put(num, 2);
			}
			idx++;
			num &= 0x3ffff;
		}

		return result;
	}

}